Round Overview
Discuss this match
You should create a variable ans, initially equal to -1. Then, with two for-loops you can iterate over all possible pairs (i, j). For each pair if s[i] != s[j] then you must calculate distance and consider it to be greater than the answer. Likely you will need a line ans = max(ans, abs(i-j)).
1
2
3
4
5
6
7
8
public int bigDistance(String s) {
int ans = -1;
for (int i = 0; i < s.length(); ++i)
for (int j = i + 1; j < s.length(); ++j)
if (s.charAt(i) != s.charAt(j))
ans = Math.max(ans, j - i); // always i < j so we don't need abs(j-i)
return ans;
}
One solution is to keep an ordered list (or set) of taken chairs. For a new guest we should iterate over the list and consider placing a new guest between every two elements of the list. For a list {5,20,50} we must consider placing a new guest before 5, between 5 and 20, between 20 and 50, and after 50.
Let’s think which exact chair we should consider for fixed interval [a,b] (e.g. between a=5 and b=20) and for \text{atLeast}[i]. Without considering the taken chair b=20 the first empty possible chair is max(a+d, \text{atLeast}[i]). If this value is between a and b and it’s not too close to b, then it is the an optimal chair to choose.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] findPositions(int[] atLeast, int d) {
// d - minimum allowed distance
int n = atLeast.length;
int ans[] = new int[n];
List < Integer > taken = new ArrayList(); // sorted
taken.add(2 * 1000 * 1000 * 1000); // infty
for (int i = 0; i < n; ++i) {
int where = 0;
if (atLeast[i]≤ taken.get(0) - d)
where = atLeast[i];
else
for (int j = 0;; ++j) {
where = Math.max(atLeast[i], d + taken.get(j));
if (where≤ taken.get(j + 1) - d)
break;
}
ans[i] = where;
taken.add(where);
Collections.sort(taken);
}
return ans;
}
After sorting the given pairs (\text{upTo}, \text{quantity}) we get the following situation. The interval [1, b] is divided into several intervals and we know the number of elements in each of them. We can solve this problem with dynamic programming.
Let \text{boolean } dp[r_{0}][r_{1}][r_{2}] be true only if it’s possible to put some numbers in the current (processed) prefix to get exactly r_i elements with remainder i. One of possible complexities is O((n/3)^6). Note that it’s enough to create an array of size dp[n/3][n/3][n/3].
Code is uploaded on Ideone: http://ideone.com/hMGRmW . I will put it here later.
This problem is slightly easier that div2-hard (BearFair2) and can be solve in the same way. But also, one can avoid the dynamic programming. After getting the division into intervals for each of them let’s find the maximum and minimum number of even elements in there. Summing up those minimums and maximums will give us the total minimum number of even elements and the total maximum number of even elements. Then it’s enough to check whether the required number of even elements (i.e. n/2) is between the total minimum and maximum.
You can see an author’s code on Ideone: http://ideone.com/sm0lwI .
You can see code on Ideone: http://ideone.com/AcUkWi . The important thing is that there is at most \log n rounds. You must find some pattern to be able to get k rounds for n = 2^k and m = n-1. It turns out that one can construct it as a path - you must care only about the order of edges. Then add some big edges anywhere to get the required number of edges.
It turns out that we can go from left to right and consider only the following two states. Either we have “x occurrences of the same letter y” taken from the left (so we want to close them somewhere on the right). Or we have “x occurrences of letters different than y” so now we collect some letters different than y and later on the right there will be many occurrences of letter y. The first situation is helpful e.g. for test “aabc” and the second one is helpful for test “abcc”. But you can fail on test “aabbcc” and there is one more trick. It turns out that from the state “x occurrences of letter y” we must always consider it also as “x occurrences of letters different than y2” for every y2 different than y. It’s enough to do the following dynamic programming and you can see my code for details - http://ideone.com/KhwmSW . Below you can see the main proof.
There exists an optimal solution that the following two lemmas hold (without proof now):
Lemma A - For any vertical line let’s consider all pairs intersecting it. Either they all have the same left letter or they all have the same right letter.
Lemma B - There are no two pairs intersecting with themselves. In other words, there is no quadruple of indices a < b < c < d that we pair a with c and we pair b with d.
Let’s consider some solution satisfying the given two lemmas. Pairs form a forest structure with some roots - pairs not being inside of any other pair. Let’s call such big pairs superior. Each superior pair with pairs inside form a single tree. For such a tree the following holds:
Super-Lemma - In some prefix all left endpoints of pairs contain the same letter. Then, in the remaining suffix all right endpoints contain the same letter.
Let’s prove the Super-Lemma. We must analyse a single tree, defined by some superior pair S. Let a and z denote left and right letter of S respectively ( a \ne z). The Super-Lemma says that in some prefix all left letters are equal to a, and in the remaining suffix all right letters are equal to z. The lemma is trivially satisfied if all left letters are equal to a, or if all right letters are equal to z. Otherwise, let i denote an index of the first left letter different than a, and let j denote an index of the last right letter different than z (note that i \ne j). The Super-Lemma can be formulated as i \gt j. Let’s prove it by contradiction.
We assume i \lt j. Indices i and j can’t be endpoints of the same pair because this pair would be inside of S and Lemma A wouldn’t hold for a vertical line intersecting this pair and pair S. Now, let P denote a pair with left endpoint in i, and let Q denote a pair with right endpoint in j. If one of P, Q was inside of the other one then Lemma A wouldn’t hold for a vertical line intersecting P, Q, S. Lemma B implies that P and Q don’t intersect with each other. Thus, the remaining case is that P is on the left from Q. Note that it doesn’t mean they are e.g. close to each other. DRAWING TODO
OLD VERSION BELOW, do not read. Lemma B implies that i can’t be paired with index on the right * sadflkjasdf * saldkfjas In prefix mentioned in the Super-Lemma all left endpoints must contain a letter a. Let P denote the first pair with some other letter in left endpoint. Let’s consider a vertical line after its left endpoint. Not all pairs intersecting with this line have the same left endpoint because a superior pair and pair P have different left letters. Lemma A says that all right endpoints must be the same then. The same will hold as we move to the right till we encounter the right endpoint of pair P. Because later a vertical line doesn’t intersect with P so maybe Lemma A is again satisfied with “all left endpoints are the same” instead of “all right endpoints”. But we want to prove that all right endpoints are the same from this moment to the end.
Let’s consider the first pair Q with right endpoint different than x (because x is right endpoint of a superior pair). Note that pair Q is on the right from pair P (though it doesn’t mean that they the same parent in a tree-structure). Considering a vertical line after the left endpoint of Q shows that left endpoints of Q and a superior pair must be the same. It means that Q has letters a and x’ in endpoints where x’ denotes something different than x. Pair P has letters a’ and x. We have order left[superior], left[P], right[P], left[Q], right[Q], right[superior]. But with listed observations we can join them into pairs to get strictly better solution: left[superior]+left[P], right[P]+left[Q], right[Q]+right[superior]. We got contradiction.